Conversione da Postfisso a Prefisso

Obiettivo

Il tuo obiettivo è convertire un'espressione espressione postfissa (Notazione Polacca Inversa) nel suo equivalente espressione prefissa (Notazione Polacca) costruendo e attraversando un albero espressione.

Algoritmo

1. Costruisci l'albero delle espressioni: Elabora l'espressione postfissa da sinistra a destra utilizzando uno stack.
   • Quando viene trovato un operando (ad esempio A, B), crea un albero con un solo nodo per esso e inseriscilo nello stack.
   • Quando viene trovato un operatore (ad esempio +, *) viene trovato, estrai due alberi dallo stack. Il primo estratto è il figlio destro (T₂) e il secondo è il figlio sinistro (T₁). Crea un nuovo albero con l'operatore come radice e reinseriscilo nello stack.
2. Genera la stringa prefissa: Dopo aver elaborato tutti i token, lo stack conterrà l'albero completo dell'espressione. Esegui un'attraversamento in preordine (Radice → Sinistra → Destra) su questo albero per produrre l'espressione prefissa finale.

Esempio

Per l'espressione postfissa A B + C *, l'algoritmo costruisce l'albero seguente:

  *
   / \
  +   C
 / \
A   B

Un attraversamento in preordine produce l'espressione prefissa: * + A B C.

Formato Input/Output

Input

• Riga 1: Un numero intero N (1 ≤ N ≤ 1000), il numero di token.
• Riga 2: L'espressione postfissa, con N token separati da spazi.

Regole dei token

• Operandi: Lettere maiuscole singole (A-Z).
• Operatori: I quattro operatori binari: +, -, *, /.

Output

• Una sola riga contenente l'espressione prefissa corrispondente, con i token separati da spazi.

Esempi

Esempio 1:

5

A B + C *

* + A B C

Esempio 2:

7

A B C * + D /

/ + A * B C D

Esempio 3:

7

A B + C D - *

* + A B - C D

Limitazioni